上海理工大学2021年869数据结构及软件工程考研大纲

第一部分：数据结构

一、参考书目

《数据结构》（C语言版），严蔚敏等主编，清华大学出版社，2012年

二、 考试内容要求

1、了解数据结构及其分类、数据结构与算法的密切关系。

2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。

3、掌握设计算法的步骤和算法分析方法。

4、掌握数据结构在排序和查找等常用算法中的应用。

5、初步掌握文件组织方法和索引技术。

三、考试内容

1、 数据结构基本概念及简单的算法分析

1)什么是数据结构

2) 抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言

3) 数据结构的抽象层次

4) 算法定义

5) 性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂.

2、 数组

1)作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组；数组的顺序存储方式

2)顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例

3) 字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配

3、链表

1) 单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；单链表的游标类；静态链表

2) 循环链表：循环链表的类定义；用循环链表解约瑟夫问题；多项式及其相加：多项式的类定义；多项式的加法

3) 双向链表

4、栈和队列

1) 栈：栈的抽象数据类型；栈的顺序存储表示；栈的